import java.util.HashMap;
import java.util.Map;

public class Test {
    public int subarraysDivByK(int[] nums, int k) {
        int count = 0;
        int prefixSum = 0;
        int[] modCount = new int[k];
        modCount[0] = 1;

        for (int num : nums) {
            prefixSum += num;
            int mod = ((prefixSum % k) + k) % k;

            count += modCount[mod];
            modCount[mod]++;
        }

        return count;
    }

    public int subarraysDivByK1(int[] nums, int k) {
        Map<Integer, Integer> hash=new HashMap<>();
        hash.put(0%k,1);
        int sum=0,ret=0;
        for(int x:nums){
            sum+=x;//计算当前位置前缀和
            int m=(sum%k+k)%k;//当前前缀和余数
            ret+=hash.getOrDefault(m,0);
            hash.put(m,hash.getOrDefault(m,0)+1);
        }
        return ret;
    }
    public static void main(String[] args) {
        int[] nums = {4,5,0,-2,-3,1};
        int k = 5;
        Test test = new Test();
        System.out.println(test.subarraysDivByK1(nums, k));
    }
}
